//给定两个用链表表示的整数，每个节点包含一个数位。 
//
// 这些数位是反向存放的，也就是个位排在链表首部。 
//
// 编写函数对这两个整数求和，并用链表形式返回结果。 
//
// 
//
// 示例： 
//
// 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
//输出：2 -> 1 -> 9，即912
// 
//
// 进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢? 
//
// 示例： 
//
// 输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
//输出：9 -> 1 -> 2，即912
// 
// Related Topics 递归 链表 数学 👍 140 👎 0


package leetcode.editor.cn;

/**
 * 链表求和
 * @date 2022-07-20 15:55:44
 */
class P0205_SumListsLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new P0205_SumListsLcci().new Solution();
		  ListNode l1 = new ListNode(7);
		  l1.next = new ListNode(1);
		  l1.next.next = new ListNode(6);
		  ListNode l2 = new ListNode(5);
		  l2.next = new ListNode(9);
		  l2.next.next = new ListNode(2);
		  ListNode res = solution.addTwoNumbers3(l1,l2);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
	public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
		int res = sum(l1)+sum(l2);
		ListNode dummyhead = new ListNode(-1);
		ListNode p = dummyhead;
		while(res != 0){
			int temp = res % 10;
			res = res/10;
			ListNode tempnode = new ListNode(temp);
			p.next = tempnode;
			p = tempnode;
		}
		return dummyhead.next;
	}
	public int sum(ListNode l){
		if(l == null){
			return 0;
		}
		ListNode p = l;
		int res = 0;
		int i = 0;
		while(p != null){
			res+=Math.pow(10,i++)*p.val;
			p = p.next;
		}
		return res;
	}
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode res = new ListNode(-1);
		ListNode temp = res;
		int t = 0;//存储相加的和
		while(l1 != null || l2 != null || t!=0){
			if(l1 != null){
				t+=l1.val;
				l1 = l1.next;
			}
			if(l2 != null){
				t+= l2.val;
				l2=l2.next;
			}
			temp.next = new ListNode(t%10);
			temp = temp.next;
			t = t/10;//用于保存进位
		}
		return res.next;
	}
	public ListNode addTwoNumbers3(ListNode l1, ListNode l2) {
		ListNode t1 = reverselist(l1);
		ListNode t2 = reverselist(l2);
		return addTwoNumbers(t1,t2);
	}
	public ListNode reverselist(ListNode l){
		ListNode dummyhead = new ListNode(-1);
		ListNode p = l;
		while(p != null){
			ListNode temp = p.next;
			p.next = dummyhead.next;
			dummyhead.next = p;
			p = temp;
		}
		return dummyhead.next;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
